package ljl.alg.jianzhioffer.round2;

import java.util.LinkedList;

public class _59_2_max_in_queue {
    
    /**
     * 和 min stack 有啥区别？
     *
     * 本以为跟喝水一样简单。。结果做错了！
     *
     * 改了一版，又错了。。
     *   把 peekFirst 改成 peekLast 还是不对
     *
     * 不能生搬硬套。。这个和 min stack 不一样
     * 那个是一个口进出，这个是一个口进一个口出
     * 当大数出去后，最大值可能就变了，这个比较麻烦！
     *
     * 估计得用单调队列了，后面的大数，会把前面小数挤出去
     * 后面的小数，会入队
     * 出队，如果出队的数和大数相等，大数队列也要出队
     *
     * 这次对了。。我可没看答案啊！
     *
     * */
    class MaxQueue {
        
        LinkedList<Integer> maxQ = new LinkedList<>();
        LinkedList<Integer> q = new LinkedList<>();
        
        public int max_value() {
            return maxQ.isEmpty() ? -1 : maxQ.peekFirst();
        }
        
        public void push_back(int value) {
            q.offer(value);
            while (!maxQ.isEmpty() && value > maxQ.peekLast())
                maxQ.pollLast();
            maxQ.offer(value);
        }
        
        public int pop_front() {
            if (q.isEmpty())
                return -1;
            int val = q.pop();
            if (maxQ.peekFirst() == val)
                maxQ.poll();
            return val;
        }
    }
}
